package cn.xdf.learn.leetcode.斐波那契;

public class 斐波那契 {

    /**
     * 定义
     * 斐波那契数列是指这样一个数列：1，1，2，3，5，8，13，21，34，55，89……这个数列从第3项开始 ，每一项都等于前两项之和。
     */

    static int fibonacci递归(int n){
        if (n ==1 || n == 2){
            return 1;
        }
        return fibonacci递归(n-1) + fibonacci递归(n-2);
    }

    /**
     * 使用迭代法，用 fn1 和 fn2 保存计算过程中的结果，并复用起来
     */
   static int Fibonacci(int number) {
        if (number <= 0) {
            return 0;
        }
        if (number == 1 || number == 2) {
            return 1;
        }
        int first = 1, second = 1, third = 0;
        for (int i = 3; i <= number; i++) {
            third = first + second;
            first = second;
            second = third;
        }
        return third;
    }

    public static void main(String[] args) {
        System.out.println(fibonacci递归(10));
        System.out.println(Fibonacci(10));
    }

}
